package com.formula.datastructure.exam.graph.traverse;

import com.formula.datastructure.standard.queue.Queue;

public class AdjListsGraph {
    AdjListsVertex[] vertexList;
    int[] visited;   // 图的遍历都需要
    public int vertexSize;
    public int edgeSize;

    public AdjListsGraph() {
        vertexList = new AdjListsVertex[50];
        visited = new int[50];
    }

    public void addVer(AdjListsVertex vertex) {
        vertexList[vertexSize++] = vertex;
    }

    // 深度有递归
    void DFS(int idx) {
        visited[idx] = 1;

        AdjListsEdge temp = vertexList[idx].firstEdge;
        while (temp != null) {
            if (visited[temp.to] == 0) {
                DFS(temp.to);
            }
            temp = temp.nextEdge;
        }
    }

    void BFS(int idx) {
        Queue<Integer> queue = new Queue<>();
        visited[idx] = 1;
        visit(vertexList[idx]);
        queue.enQueue(idx);
        while (!queue.isEmpty()) {
            AdjListsVertex tempVer = vertexList[queue.deQueue()];

            AdjListsEdge tempEdge = tempVer.firstEdge;
            while (tempEdge != null) {
                if (visited[tempEdge.to] == 0) {
                    visited[tempEdge.to] = 1;
                    visit(vertexList[tempEdge.to]);
                    queue.enQueue(tempEdge.to);
                }
                tempEdge = tempEdge.nextEdge;
            }
        }
    }

    private void visit(AdjListsVertex vertex) {
        System.out.println(vertex.data);
    }

}
